/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-04
 * Time: 23:21
 */
public class Solution {
    /**
     *  二维 dp
     * @param n
     * @return
     */
    public double[] dicesProbability(int n) {
        int row = n;
        int col = 6*n;
//         dp[i][j] 表示前 i 个骰子中, 和为 j 的概率
        // 所以均多开辟了一块空间
        double [][] dp = new double[row+1][col+1];
        // 初始化, 骰子个数为一时, 出现各点的概率都是 1/6
        for (int i = 1;i <= 6;i++) {
            dp[1][i] = 1.0 / 6;
        }
//         dp[i][j] = dp[i-1][j-1] + dp[i-1][j-1] + ... + dp[i-1][j-6];
//         但是为了防止 j - x 越界, 使用正向 dp
//         即 dp[i-1][j] 影响的范围是 dp[i][j+1], dp[i][j+2], ..., dp[i][j+6]
//         这里不用怕越界, 因为 多了一个骰子, 那么就总和的范围一定会多 6
//         所以, 这里面遍历时, 就不用 遍历最后一行
        for (int i = 1;i < row;i++) {
            // 直接从有效列开始遍历, i 个骰子最小值为 i, 最大值为 6 * i
            for (int j = i;j <= 6 * i;j++) {
                // 每个 dp[i][j] 都会影响 6 个对应的总和
                for (int k = 1;k <= 6;k++) {
                    // 注意这里不要忘了 /6 , 因为最后那个骰子出现每个点数的概率都是 1/6
                    dp[i+1][j+k] += dp[i][j]/6;
                }
            }
        }
        // 截取最后一行的有效值作为返回值
        int len = n*6 - n + 1;
        double[] ans = new double[len];
        for (int i = 0;i < len;i++) {
            ans[i] = dp[n][n+i];
        }
        return ans;
    }
}
